#define _CRT_SECURE_NO_WARNINGS
//class Solution {
//public:
//    vector<string> ans;
//    vector<vector<int>> f;
//    vector<vector<string>> ret;
//    int n;
//
//    void dfs(const string& s, int i)
//    {
//        if (i == n)
//        {
//            ret.push_back(ans);
//        }
//        for (int j = i; j < n; j++)
//        {
//            if (f[i][j])
//            {
//                ans.push_back(s.substr(i, j - i + 1));
//                dfs(s, j + 1);
//                ans.pop_back();
//            }
//        }
//
//    }
//    vector<vector<string>> partition(string s) {
//        n = s.size();
//        f.assign(n, vector<int>(n, true));
//        for (int i = n - 1; i >= 0; i--)
//        {
//            for (int j = i + 1; j < n; j++)
//            {
//
//                f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];
//            }
//        }
//
//        dfs(s, 0);
//        return ret;
//
//    }
//};
//class Solution {
//public:
//    vector<int> dailyTemperatures(vector<int>& temperatures) {
//        int length = temperatures.size();
//        vector<int> result(length, 0);
//        for (int i = 0; i < length; i++)
//        {
//            int current = temperatures[i];
//            //if(current<100)
//            for (int j = i + 1; j < length; j++)
//            {
//                if (temperatures[j] > current)
//                {
//                    result[i] = j - i;
//                    break;
//                }
//            }
//        }
//        return result;
//    }
//};
//class Solution {
//public:
//    vector<int> dailyTemperatures(vector<int>& temperatures) {
//        int n = temperatures.size();
//        vector<int> res(n, 0);
//        stack<int> st;
//        for (int i = 0; i < temperatures.size(); i++)
//        {
//            while (!st.empty() && temperatures[i] > temperatures[st.top()])
//            {
//                auto t = st.top();
//                st.pop();
//                res[t] = i - t;
//            }
//            st.push(i);
//        }
//        return res;
//
//    }
//};
//
//class Solution {
//public:
//    int largestRectangleArea(vector<int>& heights) {
//        unsigned long size = heights.size();
//        if (size == 1)
//            return heights[0];
//        int res = 0;
//        stack<int> st;
//        for (int i = 0; i < size; i++)
//        {
//            while (!st.empty() && heights[st.top()] > heights[i])
//            {
//                int length = heights[st.top()];
//                st.pop();
//                //
//                int weight = i;
//                if (!st.empty())
//                {
//                    //
//                    weight = i - st.top() - 1;
//                }
//                res = max(res, length * weight);
//            }
//            st.push(i);
//        }
//        while (!st.empty())
//        {
//            int length = heights[st.top()];
//            st.pop();
//            int weight = size;
//            if (!st.empty())
//            {
//                weight = size - st.top() - 1;
//            }
//            res = max(res, length * weight);
//        }
//        return res;
//    }
//};

//class Solution {
//public:
//    struct com
//    {
//        bool operator()(pair<int, int>& l, pair<int, int>& r)
//        {
//            return l.second > r.second;
//        }
//    };
//    vector<int> topKFrequent(vector<int>& nums, int k) {
//        unordered_map<int, int> hash;
//        priority_queue<pair<int, int>, vector<pair<int, int>>, com> pq;
//        for (auto e : nums)
//        {
//            hash[e]++;
//        }
//        for (auto& e : hash)
//        {
//            if (pq.size() < k)
//                pq.push(e);
//            else
//            {
//                if (e.second > pq.top().second)
//                {
//                    pq.pop();
//                    pq.push(e);
//                }
//            }
//        }
//        vector<int> ret;
//        while (!pq.empty())
//        {
//            ret.push_back(pq.top().first);
//            pq.pop();
//        }
//        return ret;
//    }
//};